#include <bits/stdc++.h>
#include <vector>
#include <string>

using namespace std;

/**
 * 给你两个字符串数组 queries 和 dictionary 。数组中所有单词都只包含小写英文字母，且长度都相同。

一次 编辑 中，你可以从 queries 中选择一个单词，将任意一个字母修改成任何其他字母。从 queries 中找到所有满足以下条件的字符串：不超过 两次编辑内，字符串与 dictionary 中某个字符串相同。

请你返回 queries 中的单词列表，这些单词距离 dictionary 中的单词 编辑次数 不超过 两次 。单词返回的顺序需要与 queries 中原本顺序相同。

 

示例 1：

输入：queries = ["word","note","ants","wood"], dictionary = ["wood","joke","moat"]
输出：["word","note","wood"]
解释：
- 将 "word" 中的 'r' 换成 'o' ，得到 dictionary 中的单词 "wood" 。
- 将 "note" 中的 'n' 换成 'j' 且将 't' 换成 'k' ，得到 "joke" 。
- "ants" 需要超过 2 次编辑才能得到 dictionary 中的单词。
- "wood" 不需要修改（0 次编辑），就得到 dictionary 中相同的单词。
所以我们返回 ["word","note","wood"] 。
示例 2：

输入：queries = ["yes"], dictionary = ["not"]
输出：[]
解释：
"yes" 需要超过 2 次编辑才能得到 "not" 。
所以我们返回空数组。
 

提示：

1 <= queries.length, dictionary.length <= 100
n == queries[i].length == dictionary[j].length
1 <= n <= 100
所有 queries[i] 和 dictionary[j] 都只包含小写英文字母。
 */

// 法一

// 需要从 queries 中选取每个单词，检查它与 dictionary 中每个单词之间的编辑距离是否不超过两次。
class Solution {
    public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        for(const string& query : queries) {
            bool valid = false;
            for(const string& word : dictionary) {
                // 计算编辑距离
                int diff = 0;
                for(int i = 0; i < query.size(); ++i) {
                    if(query[i] != word[i]) {
                        diff++;
                    }
                }
                // 距离不超过2就满足条件
                if(diff <= 2) {
                    valid = true;
                    break;
                }
            }
            // 辅助标记
            if(valid)   ans.push_back(query);
        }
        return ans;
    }
};

// 法二
class Solution 
{
public:
    // 主函数，接收查询数组 `queries` 和字典数组 `dictionary`，返回满足条件的查询单词
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) 
    {
        vector<string> result;  // 用来存储符合条件的查询单词
        // 遍历每个查询单词，检查其是否符合要求
        for (const auto& word : queries) 
        {
            // 如果当前单词满足条件，则将其加入结果数组
            if (helper(word, dictionary)) 
                result.emplace_back(word);
        }
        return result;  // 返回所有符合条件的查询单词
    }

private:
    // 辅助函数，检查一个单词是否与字典中的某个单词的编辑距离不超过 2
    bool helper(string word, vector<string>& dictionary) 
    {
        // 遍历字典中的每个单词
        for (const auto& s : dictionary) 
        {
            int cur = 0;  // 用于记录当前编辑距离
            int n = word.size();  // 获取单词的长度
            
            // 比较查询单词和字典单词的每个字符，计算编辑距离
            for (int i = 0; i < n and cur <= 2; i++) 
            {
                // 如果字符不同，增加编辑距离
                cur += s[i] != word[i];
            }
            
            // 如果编辑距离不超过 2，则认为符合条件，返回 true
            if (cur <= 2) return true;
        }
        // 如果所有字典单词都无法满足条件，则返回 false
        return false;
    }
};

